Privacy in data publishing.
We propose a modeling of the problem of privacy-compliant data publishing that captures confidentiality constraints on one side and visibility requirements on the other side. Confidentiality constraints express the fact that some attributes, or associations among them, are sensitive and cannot be released. Visibility requirements express requests for views over data that should be provided. We propose a solution based on data fragmentation to split sensitive associations while ensuring visibility. In addition, we show how sensitive associations broken by fragmentation can be released in a sanitized form as loose associations formed in a way to guarantee a specified degree of privacy. 1.
Differential privacy via wavelet transforms.

Search in social networks with access control.
More and more important data is accumulated inside social networks. Limiting the flow of private information across a social network is very important, and most social networks provide sophisticated privacy settings to control this flow. Creating such extensive access control knobs makes the search for content a hard problem since each user sees a unique subset of all the data. In this work, we take a first step at integrating access control based on a social network in a search system. We describe a set of solutions to the problem, including what indexes to construct and how to filter out inaccessible results. An experimental analysis illustrates the tradeoffs of the various strategies, and we point out a set of interesting future research directions in this area.
Behavioral Simulations in MapReduce
In many scientific domains, researchers are turning to large-scale behavioral simulations to better understand real-world phenomena. While there has been a great deal of work on simulation tools from the high-performance computing community, behavioral simulations remain challenging to program and automatically scale in parallel environments. In this paper we present BRACE (Big Red Agent-based Computation Engine), which extends the MapReduce framework to process these simulations efficiently across a cluster. We can leverage spatial locality to treat behavioral simulations as iterated spatial joins and greatly reduce the communication between nodes. In our experiments we achieve nearly linear scale-up on several realistic simulations. Though processing behavioral simulations in parallel as iterated spatial joins can be very efficient, it can be much simpler for the domain scientists to program the behavior of a single agent. Furthermore, many simulations include a considerable amount of complex computation and message passing between agents, which makes it important to optimize the performance of a single node and the communication across nodes. To address both of these challenges, BRACE includes a high-level language called BRASIL (the Big Red Agent SImulation Language). BRASIL has object-oriented features for programming simulations, but can be compiled to a dataflow representation for automatic parallelization and optimization. We show that by using various optimization techniques, we can achieve both scalability and single-node performance similar to that of a hand-coded simulation. 1.
Programming with differential privacy technical persepctive.

Programming with differential privacy technical persepctive.

Behavioral Simulations in MapReduce.
In many scientific domains, researchers are turning to large-scale behavioral simulations to better understand real-world phenomena. While there has been a great deal of work on simulation tools from the high-performance computing community, behavioral simulations remain challenging to program and automatically scale in parallel environments. In this paper we present BRACE (Big Red Agent-based Computation Engine), which extends the MapReduce framework to process these simulations efficiently across a cluster. We can leverage spatial locality to treat behavioral simulations as iterated spatial joins and greatly reduce the communication between nodes. In our experiments we achieve nearly linear scale-up on several realistic simulations. Though processing behavioral simulations in parallel as iterated spatial joins can be very efficient, it can be much simpler for the domain scientists to program the behavior of a single agent. Furthermore, many simulations include a considerable amount of complex computation and message passing between agents, which makes it important to optimize the performance of a single node and the communication across nodes. To address both of these challenges, BRACE includes a high-level language called BRASIL (the Big Red Agent SImulation Language). BRASIL has object-oriented features for programming simulations, but can be compiled to a dataflow representation for automatic parallelization and optimization. We show that by using various optimization techniques, we can achieve both scalability and single-node performance similar to that of a hand-coded simulation. 1.
Beyond isolation research opportunities in declarative data%2Ddriven coordination.
There are many database applications that require users to coordinate and communicate. Friends want to coordinate travel plans, students want to jointly enroll in the same set of courses, and busy professionals want to coordinate their schedules. These tasks are difficult to program using existing abstractions provided by database systems because in addition to the traditional ACID properties provided by the system they all require some type of coordination between users. This is fundamentally incompatible with isolation in the classical ACID properties. In this position paper, we argue that it is time for the database community to look beyond isolation towards principled and elegant abstractions that allow for communication and coordination between some notion of (suitably generalized)
From Declarative Languages to Declarative Processing in Computer Games.
Recent work has shown that we can dramatically improve the performance of computer games and simulations through declarative processing: Character AI can be written in an imperative scripting language which is then compiled to relational algebra and executed by a special games engine with features similar to a main memory database system. In this paper we lay out a challenging research agenda built on these ideas. We discuss several research ideas for novel language features to support atomic actions and reactive programming. We also explore challenges for main memory query processing in games and simulations including adaptive query plan selection, support for multi-core and parallel architectures, debugging simulation scripts, and extensions for multi-player games and virtual worlds. We believe that these research challenges will result in a dramatic change in the design of game engines over the next decade. 1.
Inverted indexes vs. bitmap indexes in decision support systems.
Bitmap indexes are widely used in Decision Support Systems (DSSs) to improve query performance. In this paper, we evaluate the use of compressed inverted indexes with adapted query processing strategies from Information Retrieval as an alternative. In a thorough experimental evaluation on both synthetic data and data from the Star Schema Benchmark, we show that inverted indexes are more compact than bitmap indexes in almost all cases. This compactness combined with efficient query processing strategies results in inverted indexes outperforming bitmap indexes for most queries, often significantly.
Distributed event stream processing with non%2Ddeterministic finite automata.
Efficient matching of incoming events to persistent queries is fundamental to event pattern matching, complex event processing, and publish/subscribe systems. Recent processing engines based on non-deterministic finite automata (NFAs) have demonstrated scalability in the number of queries that can be efficiently executed on a single machine. However, existing NFA based systems are limited to processing events on a single machine. Consequently, their event processing capacity cannot be increased by adding more machines. In this paper, we present an experimental evaluation of different methods for distributing an event processing system that is based on NFAs across multiple machines in a cluster. Our results show that careful input stream partitioning gives close to linear performance scaleup for CPU bound workloads.
Rule%2Dbased multi%2Dquery optimization.
Data stream management systems usually have to process many long-running queries that are active at the same time. Multiple queries can be evaluated more efficiently together than independently, because it is often possible to share state and computation. Motivated by this observation, various Multi-Query Optimization (MQO) techniques have been proposed. However, these approaches suffer from two limitations. First, they focus on very specialized workloads. Second, integrating MQO techniques for CQL-style stream engines and those for event pattern detection engines is even harder, as the processing models of these two types of stream engines are radically different. In this paper, we propose a rule-based MQO framework. This framework incorporates a set of new abstractions, extending their counterparts, physical operators, transformation rules, and streams, in a traditional RDBMS or stream processing system. Within this framework, we can integrate new and existing MQO techniques through the use of transformation rules. This allows us to build an expressive and scalable stream system. Just as relational optimizers are crucial for the success of RDBMSes, a powerful multi-query optimizer is needed for data stream processing. This work lays the foundation for such a multi-query optimizer, creating opportunities for future research. We experimentally demonstrate the efficacy of our approach. 1.
Scalability for Virtual Worlds.

Database research in computer games.
This tutorial presents an overview of the data management issues faced by computer games today. While many games do not use databases directly, they still have to process large amounts of data, and could benefit from the application of database technology. Other games, such as massively multiplayer online games (MMOs), must communicate with commercial databases and have their own unique challenges. In this tutorial we will present the state-of-the-art of data management in games that we learned from our interaction with various game studios. We will show how the issues involved motivate current research, and illustrate several possibilities for future work. Our tutorial will start with a description of data-driven design, which is the source of many of the data management issues that games face. We will show some of the tools that game developers use to create and manage content. We will discuss how this type of design can affect performance, and the data structures and techniques that developers use to ensure that the game is responsive. We will discuss the problem of consistency in games, and how games ensure that players all share the same view of the world. Finally, we will examine some of the engineering issues that game developers have to deal with when interacting with traditional databases. This tutorial is intended to be self-contained, and provides the background necessary for understanding how databases and database technology are relevant to computer games. This tutorial is accessible to students and researchers who, while perhaps not hardcore gamers themselves, are interested in ways in which they can use their expertise to solve problems in computer games.
Interactive anonymization of sensitive data.
There has been much recent work on algorithms for limiting disclosure in data publishing. However, these algorithms have not been put to use in any comprehensive, usable toolkit for practicioners. We will demonstrate CAT, the Cornell Anonymization Toolkit, designed for interactive anonymization. CAT has an interface that is easy to use; it guides users through the process of preparing a dataset for publication while limiting disclosure through the identification of records that have high risk under various attacker models.
Event and Pattern Detection over Streams.

Randomization Methods to Ensure Data Privacy.

Scalable Decision Tree Construction.
Classification is an important data mining problem. Given a training database of records, each tagged with a class label, the goal of classification is to build a concise model that can be used to predict the class label of future, unlabeled records. A very popular class of classifiers are decision trees. All current algorithms to construct decision trees, including all main-memory algorithms, make one scan over the training database per level of the tree.  We introduce a new algorithm (BOAT) for decision tree construction that improves upon earlier algorithms in both performance and functionality. BOAT constructs several levels of the tree in only two scans over the training database, resulting in an average performance gain of 300% over previous work. The key to this performance improvement is a novel optimistic approach to tree construction in which we construct an initial tree using a small subset of the data and refine it to arrive at the final tree. We guarantee that any differen...
Continuous Queries in Sensor Networks.
Data compression issues arise in a sensor network when designing protocols for efficiently collecting all data observed by the sensor nodes at an Internet-connected base station. More formally, let Xi denote an attribute being observed by a node in the sensor network – Xi may be an environmental property being sensed by the node (e.g., temperature), or it may be the result of an operation on the sensed values (e.g., in an anomaly-detection application, the sensor node may continuously evaluate a filter such as “temperature&gt; 100 ” on the observed values). The goal is to design an energy-efficient protocol to periodically collect the observed values of all such attributes (denoted X1,  ·  ·  · , Xn) at the base station, at a frequency specified by the user. In many cases, a bounded-error approximation might be acceptable, ie., the reported values may only be required to be within ±ɛ of the observed values, for a given ɛ. The typical optimization metric is the total energy expended during the data collection process, commonly approximated by the total communication cost; however, metrics such as minimizing the maximum energy consumption across all nodes or maximizing the lifetime of the sensor network may also be appropriate in some settings. MAIN TEXT The key issue in designing data collection protocols is modeling and exploiting the strong spatio-temporal correlations present in most sensor networks. Let X t i be a random variable that denotes the value of Xi at
Database Techniques to Improve Scientific Simulations.

DBMS Component.
This paper describes the KIDS  1  approach to database management system (DBMS) construction. KIDS aims at the development of a DBMS-construction approach by defining specification-based approaches strongly relying on software reuse. We propose an architecture model that supports reuse of architectures, but is also able to integrate various DBMS components into a coherent entirety. Second, KIDS defines a construction process model that strives for reuse in all phases. We have identified three important aspects that are initially addressed by the construction approach: the data model aspect, the transaction management aspect, and the integrity management aspect. For each of these aspects, a customized approach how to construct the corresponding subsystem has been developed, again relying on software reuse wherever possible. While these aspects have been considered because of their relevance for any DBMS, the construction method is open for further aspects.  Keywords: Database management...
DBMS Interface.
A federated database system (FDBS) is a collection of cooperating database systems that are autonomous and possibly heterogeneous. In this paper, we define a reference architecture for distributed database management systems from system and schema viewpoints and show how various FDBS architectures can be developed. We then define a methodology for developing one of the popular architectures of an FDBS. Finally, we discuss critical issues related to developing and operating an FDBS.
Privacy in Search Logs

From Declarative Languages to Declarative Processing in Computer Games
Recent work has shown that we can dramatically improve the performance of computer games and simulations through declarative processing: Character AI can be written in an imperative scripting language which is then compiled to relational algebra and executed by a special games engine with features similar to a main memory database system. In this paper we lay out a challenging research agenda built on these ideas. We discuss several research ideas for novel language features to support atomic actions and reactive programming. We also explore challenges for main memory query processing in games and simulations including adaptive query plan selection, support for multi-core and parallel architectures, debugging simulation scripts, and extensions for multi-player games and virtual worlds. We believe that these research challenges will result in a dramatic change in the design of game engines over the next decade. 1.
From Declarative Languages to Declarative Processing in Computer Games
Recent work has shown that we can dramatically improve the performance of computer games and simulations through declarative processing: Character AI can be written in an imperative scripting language which is then compiled to relational algebra and executed by a special games engine with features similar to a main memory database system. In this paper we lay out a challenging research agenda built on these ideas. We discuss several research ideas for novel language features to support atomic actions and reactive programming. We also explore challenges for main memory query processing in games and simulations including adaptive query plan selection, support for multi-core and parallel architectures, debugging simulation scripts, and extensions for multi-player games and virtual worlds. We believe that these research challenges will result in a dramatic change in the design of game engines over the next decade. 1.
Differential Privacy via Wavelet Transforms

Technical perspective %2D Data stream processing when you only get one look.

Better scripts%2C better games.
03/2009 vol.52 no.03 cacm.acm.oRG ReBooteD! Being human in the Digital age
The Claremont report on database research.
Abstract. Query processing is one of the most important mechanisms for data management, and there exist mature techniques for effective query optimization and efficient query execution. The vast majority of these techniques assume workloads of rather small transactional tasks with strong requirements for ACID properties. However, the emergence of new computing paradigms, such as grid and cloud computing, the increasingly large volumes of data commonly processed, the need to support data driven research, intensive data analysis and new scenarios, such as processing data streams on the fly or querying web services, the fact that the metadata fed to optimizers are often missing at compile time, and the growing interest in novel optimization criteria, such as monetary cost or energy consumption, create a unique set of new requirements for query processing systems. These requirements cannot be met by modern techniques in their entirety, although interesting solutions and efficient tools have already been developed for some of them in isolation. Next generation query processors are expected to combine features addressing all of these issues, and, consequently, lie at the confluence of several research initiatives. This paper aims to present a vision for such processors, to explain their functionality requirements, and to discuss the open issues, along with their challenges. 1
Multi%2Dquery optimization for sketch%2Dbased estimation.

An Evaluation of Checkpoint Recovery for Massively Multiplayer Online Games.
Massively multiplayer online games (MMOs) have emerged as an exciting new class of applications for database technology. MMOs simulate long-lived, interactive virtual worlds, which proceed by applying updates in frames or ticks, typically at 30 or 60 Hz. In order to sustain the resulting high update rates of such games, game state is kept entirely in main memory by the game servers. Nevertheless, durability in MMOs is usually achieved by a standard DBMS implementing ARIES-style recovery. This architecture limits scalability, forcing MMO developers to either invest in high-end hardware or to over-partition their virtual worlds. In this paper, we evaluate the applicability of existing checkpoint recovery techniques developed for main-memory DBMS to MMO workloads. Our thorough experimental evaluation uses a detailed simulation model fed with update traces generated synthetically and from a prototype game server. Based on our results, we recommend MMO developers to adopt a copy-on-update scheme with a double-backup disk organization to checkpoint game state. This scheme outperforms alternatives in terms of the latency introduced in the game as well the time necessary to recover after a crash. 1.
Data Publishing against Realistic Adversaries.
Privacy in data publishing has received much attention recently. The key to defining privacy is to model knowledge of the attacker – if the attacker is assumed to know too little, the published data can be easily attacked, if the attacker is assumed to know too much, the published data has little utility. Previous work considered either quite ignorant adversaries or nearly omniscient adversaries. In this paper, we introduce a new class of adversaries that we call realistic adversaries who live in the unexplored space in between. Realistic adversaries have knowledge from external sources with an associated stubbornness indicating the strength of their knowledge. We then introduce a novel privacy framework called epsilon-privacy that allows us to guard against realistic adversaries. We also show that prior privacy definitions are instantiations of our framework. In a thorough experimental study with real census data we show that e-privacy allows us to publish data with high utility while defending against strong adversaries. 1.
Special issue best papers of VLDB 2007.

Toward Expressive and Scalable Sponsored Search Auctions.

Privacy Theory meets Practice on the Map.
Abstract — In this paper, we propose the first formal privacy analysis of a data anonymization process known as the synthetic data generation, a technique becoming popular in the statistics community. The target application for this work is a mapping program that shows the commuting patterns of the population of the United States. The source data for this application were collected by the U.S. Census Bureau, but due to privacy constraints, they cannot be used directly by the mapping program. Instead, we generate synthetic data that statistically mimic the original data while providing privacy guarantees. We use these synthetic data as a surrogate for the original data. We find that while some existing definitions of privacy are inapplicable to our target application, others are too conservative and render the synthetic data useless since they guard against privacy breaches that are very unlikely. Moreover, the data in our target application is sparse, and none of the existing solutions are tailored to anonymize sparse data. In this paper, we propose solutions to address the above issues. I.
Declarative
I declare that this dissertation is my own, unaided work. It is being submitted for
SGL a scalable language for data%2Ddriven games.

SEMMO a scalable engine for massively multiplayer online games.

Better Scripts%2C Better Games.
03/2009 vol.52 no.03 cacm.acm.oRG ReBooteD! Being human in the Digital age
Toward Expressive and Scalable Sponsored Search Auctions

Towards a streaming SQL standard.
This paper describes a unification of two different SQL extensions for streams and its associated semantics. We use the data models from Oracle and StreamBase as our examples. Oracle uses a time-based execution model while StreamBase uses a tuple-based execution model. Time-based execution provides a way to model simultaneity while tuple-based execution provides a way to react to primitive events as soon as they are seen by the system. The result is a new model that gives the user control over the granularity at which one can express simultaneity. Of course, it is possible to ignore simultaneity altogether. The proposed model captures ordering and simultaneity through partial orders on batches of tuples. The batching and the ordering are encapsulated in and can be modified by means of a powerful new operator that we call SPREAD. This paper describes the semantics of SPREAD and gives several examples of its use. 1.
Towards a streaming SQL standard.
This paper describes a unification of two different SQL extensions for streams and its associated semantics. We use the data models from Oracle and StreamBase as our examples. Oracle uses a time-based execution model while StreamBase uses a tuple-based execution model. Time-based execution provides a way to model simultaneity while tuple-based execution provides a way to react to primitive events as soon as they are seen by the system. The result is a new model that gives the user control over the granularity at which one can express simultaneity. Of course, it is possible to ignore simultaneity altogether. The proposed model captures ordering and simultaneity through partial orders on batches of tuples. The batching and the ordering are encapsulated in and can be modified by means of a powerful new operator that we call SPREAD. This paper describes the semantics of SPREAD and gives several examples of its use. 1.
Large%2Dscale collaborative analysis and extraction of web data.
Archived web data is a great resource for scientific research, but poses serious challenges in data processing and management. We demonstrate the Web Lab Collaboration Server, a platform and service for large-scale collaborative web data analysis in a distributed computing environment, and show how it seamlessly supports non-technical users during search, data extraction and analysis. 1.
The Claremont report on database research.
Abstract. Query processing is one of the most important mechanisms for data management, and there exist mature techniques for effective query optimization and efficient query execution. The vast majority of these techniques assume workloads of rather small transactional tasks with strong requirements for ACID properties. However, the emergence of new computing paradigms, such as grid and cloud computing, the increasingly large volumes of data commonly processed, the need to support data driven research, intensive data analysis and new scenarios, such as processing data streams on the fly or querying web services, the fact that the metadata fed to optimizers are often missing at compile time, and the growing interest in novel optimization criteria, such as monetary cost or energy consumption, create a unique set of new requirements for query processing systems. These requirements cannot be met by modern techniques in their entirety, although interesting solutions and efficient tools have already been developed for some of them in isolation. Next generation query processors are expected to combine features addressing all of these issues, and, consequently, lie at the confluence of several research initiatives. This paper aims to present a vision for such processors, to explain their functionality requirements, and to discuss the open issues, along with their challenges. 1
Proceedings of the 33rd International Conference on Very Large Data Bases
RESEARCH INTERESTS I am generally interested in data mining, data warehousing and database systems. My current research focuses on modeling, managing and analyzing large-scale graph and information network data.
Cayuga A General Purpose Event Monitoring System.
System for scalable event processing. We present a query language based on Cayuga Algebra for naturally expressing complex event patterns. We also describe several novel system design and implementation issues, focusing on Cayuga’s query processor, its indexing approach, how Cayuga handles simultaneous events, and its specialized garbage collector. 1.
Worst%2DCase Background Knowledge for Privacy%2DPreserving Data Publishing.
Recent work has shown the necessity of considering an attacker’s background knowledge when reasoning about privacy in data publishing. However, in practice, the data publisher does not know what background knowledge the attacker possesses. Thus, it is important to consider the worst-case. In this paper, we initiate a formal study of worst-case background knowledge. We propose a language that can express any background knowledge about the data. We provide a polynomial time algorithm to measure the amount of disclosure of sensitive information in the worst case, given that the attacker has at most k pieces of information in this language. We also provide a method to efficiently sanitize the data so that the amount of disclosure in the worst case is less than a specified threshold. 1.
High%2DSpeed Function Approximation.
We address a new learning problem where the goal is to build a predictive model that minimizes prediction time (the time taken to make a prediction) subject to a constraint on model accuracy. Our solution is a generic framework that leverages existing data mining algorithms without requiring any modifications to these algorithms. We show a first application of our framework to a combustion simulation problem. Our experimental evaluation shows significant improvements over existing methods; prediction time typically is improved by a factor between 2 and 6. 1.
What is %22next%22 in event processing%3F
Networked sensors-those that coordinate amongst them-selves to achieve a larger sensing task-will revolutionize information gathering and processing both in urban envi-ronments and in inhospitable terrain. The sheer numbers of these sensors and the expected dynamics in these environ-ments present unique challenges in the design of unattended autonomous sensor networks. These challenges lead us to hypothesize that sensor network coordination applications may need to be structured differently from traditional net-work applications. In particular, we believe that localized algorithms (in which simple local node behavior achieves a desired global objective) may be necessary for sensor net-work coordination. In this paper, we describe localized al-gorithms, and then discuss directed diffusion, a simple com-munication model for describing localized algorithms. 1
Cayuga a high%2Dperformance event processing engine.

User%2Dcentric personalized extensibility for data%2Ddriven web applications.

P%2Dring an efficient and robust P2P range index structure.

A unified platform for data driven web applications with automatic client%2Dserver partitioning.

Scaling games to epic proportion.

Massively multi%2Dquery join processing in publish%2Fsubscribe systems.
There has been much recent interest in XML publish/subscribe systems. Some systems scale to thousands of concurrent queries, but support a limited query language (usually a fragment of XPath 1.0). Other systems support more expressive languages, but do not scale well with the number of concurrent queries. In this paper, we propose a set of novel query processing techniques, referred to as Massively Multi-Query Join Processing techniques, for processing a large number of XML stream queries involving value joins over multiple XML streams and documents. These techniques enable the sharing of representations of inputs to multiple joins, and the sharing of join computation. Our techniques are also applicable to relational event processing systems and publish/subscribe systems that support join queries. We present experimental results to demonstrate the effectiveness of our techniques. We are able to process thousands of XML messages with hundreds of thousands of join queries on real RSS feed streams. Our techniques gain more than two orders of magnitude speedup compared to the naive approach of evaluating such join queries.
A unified platform for data driven web applications with automatic client%2Dserver partitioning.

Worst%2DCase Background Knowledge for Privacy%2DPreserving Data Publishing
Recent work has shown the necessity of considering an attacker’s background knowledge when reasoning about privacy in data publishing. However, in practice, the data publisher does not know what background knowledge the attacker possesses. Thus, it is important to consider the worst-case. In this paper, we initiate a formal study of worst-case background knowledge. We propose a language that can express any background knowledge about the data. We provide a polynomial time algorithm to measure the amount of disclosure of sensitive information in the worst case, given that the attacker has at most k pieces of information in this language. We also provide a method to efficiently sanitize the data so that the amount of disclosure in the worst case is less than a specified threshold. 1.
Plagiarism Detection in arXiv
We describe a large-scale application of methods for finding plagiarism in research document collections. The methods are applied to a collection of 284,834 documents collected by arXiv.org over a 14 year period, covering a few different research disciplines. The methodology efficiently detects a variety of problematic author behaviors, and heuristics are developed to reduce the number of false positives. The methods are also efficient enough to implement as a real-time submission screen for a collection many times larger. 1.
Index structures for matching XML twigs using relational query processors.
Various index structures have been proposed to speed up the evaluation of XML path expressions. However, existing XML path indices su#er from at least one of three limitations: they focus only on indexing the structure (relying on a separate index for node content), they are useful only for simple path expressions such as root-to-leaf paths, or they cannot be tightly integrated with a relational query processor. Moreover, there is no unified framework to compare these index structures. In this paper, we present a framework defining a family of index structures that includes most existing XML path indices. We also propose two novel index structures in this family, with different space-time tradeo#s, that are e#ective for the evaluation of XML branching path expressions (i.e., twigs) with value conditions. We also show how this family of index structures can be implemented using the access methods of the underlying database system. Finally, we present an experimental evaluation that shows the performance tradeo# between index space and matching time. The experimental results show that our novel indices achieve orders of magnitude improvement in performance for evaluating twig queries, albeit at a higher space cost, over the use of previously proposed XML path indices that can be tightly integrated with a relational query processor.
Database research opportunities in computer games.
In this paper, we outline several ways in which the database community can contribute to the development of technology for computer games. We outline the architecture of different types of computer games, and show how database technology plays a role in their design. From this, we identify several new research directions to improve the utilization of this technology in computer games. 1.
L%2Ddiversity Privacy beyond k%2Danonymity.

Wave scheduling and routing in sensor networks.

Network scheduling for data archiving applications in sensor networks.
Since data archiving in sensor networks is a communication intensive application, a careful power management of communication is of critical importance for such networks. An example is FPS, an adaptive power scheduling algorithm that combines slotted scheduling with a CSMA MAC [7]. In this paper, we first propose a new global power scheduling protocol called Multi-Flow Power Scheduling (MPS) that delivers more data and consumes less energy than existing power scheduling protocols. MPS sets up a transmission schedule through standard data aggregation and dissemination operations, however since it creates a global schedule it does not scale to large networks. We then present a new power scheduling protocol called Hybrid Power Scheduling (HPS) that retains the scalability of FPS while maintaining the energy efficiency and high data delivery rate of MPS. In a thorough simulation study, we compare HPS and MPS, and our results show the efficacy of HPS. 1.
Towards Expressive Publish%2FSubscribe Systems.
Abstract. Traditional content based publish/subscribe (pub/sub) systems allow users to express stateless subscriptions evaluated on individual events. However, many applications such as monitoring RSS streams, stock tickers, or management of RFID data streams require the ability to handle stateful subscriptions. In this paper, we introduce Cayuga, a stateful pub/sub system based on nondeterministic finite state automata (NFA). Cayuga allows users to express subscriptions that span multiple events, and it supports powerful language features such as parameterization and aggregation, which significantly extend the expressive power of standard pub/sub systems. Based on a set of formally defined language operators, the subscription language of Cayuga provides non-ambiguous subscription semantics as well as unique opportunities for optimizations. We experimentally demonstrate that common optimization techniques used in NFA-based systems such as state merging have only limited effectiveness, and we propose novel efficient indexing methods to speed up subscription processing. In a thorough experimental evaluation we show the efficacy of our approach. 1
Models and Methods for Privacy%2DPreserving Data Analysis and Publishing.

Hilda A High%2DLevel Language for Data%2DDrivenWeb Applications.
We propose Hilda, a high-level language for developing data-driven web applications. The primary benefits of Hilda over existing development platforms are: (a) it uses a unified data model for all layers of the application, (b) it is declarative, (c) it models both application queries and updates, (d) it supports structured programming for web sites, and (e) it enables conflict detection for concurrent updates. We also describe the implementation of a simple proof-ofconcept Hilda compiler, which translates a Hilda application program into Java Servlet code. 1.
Trusted CVS.
With real-time certificate validation checking, a public-key-using system that needs to validate a certificate  executes a transaction with a specialized validation party.
Three Case Studies of Large%2DScale Data Flows.

Plagiarism Detection in arXiv.
We describe a large-scale application of methods for finding plagiarism in research document collections. The methods are applied to a collection of 284,834 documents collected by arXiv.org over a 14 year period, covering a few different research disciplines. The methodology efficiently detects a variety of problematic author behaviors, and heuristics are developed to reduce the number of false positives. The methods are also efficient enough to implement as a real-time submission screen for a collection many times larger. 1.
On the efficiency of checking perfect privacy.

Injecting utility into anonymized datasets.

Automatic client%2Dserver partitioning of data%2Ddriven web applications.
An important class of applications are data-driven web applications, i.e., web applications that run on top of a back-end database system. Examples of such applications include online shopping sites, online auctions, and businessto-business
Indexing for Function Approximation.

Guest Editors%27 Introduction Sensor%2DNetwork Applications.

Processing High%2DSpeed Intelligence Feeds in Real%2DTime.

Multi%2Dquery Optimization for Sensor Networks.
Abstract. The widespread dissemination of small-scale sensor nodes has sparked interest in a powerful new database abstraction for sensor networks: Clients “program” the sensors through queries in a high-level declarative language permitting the system to perform the low-level optimizations necessary for energy-efficient query processing. In this paper we consider multi-query optimization for aggregate queries on sensor networks. We develop a set of distributed algorithms for processing multiple queries that incur minimum communication while observing the computational limitations of the sensor nodes. Our algorithms support incremental changes to the set of active queries and allow for local repairs to routes in response to node failures. A thorough experimental analysis shows that our approach results in significant energy savings, compared to previous work. 1
Index Structures for Matching XML Twigs Using Relational Query Processors.
Various index structures have been proposed to speed up the evaluation of XML path expressions. However, existing XML path indices su#er from at least one of three limitations: they focus only on indexing the structure (relying on a separate index for node content), they are useful only for simple path expressions such as root-to-leaf paths, or they cannot be tightly integrated with a relational query processor. Moreover, there is no unified framework to compare these index structures. In this paper, we present a framework defining a family of index structures that includes most existing XML path indices. We also propose two novel index structures in this family, with different space-time tradeo#s, that are e#ective for the evaluation of XML branching path expressions (i.e., twigs) with value conditions. We also show how this family of index structures can be implemented using the access methods of the underlying database system. Finally, we present an experimental evaluation that shows the performance tradeo# between index space and matching time. The experimental results show that our novel indices achieve orders of magnitude improvement in performance for evaluating twig queries, albeit at a higher space cost, over the use of previously proposed XML path indices that can be tightly integrated with a relational query processor.
Processing High%2DSpeed Intelligence Feeds in Real%2DTime.

Models and methods for privacy%2Dpreserving data publishing and analysis invited tutorial.

Guaranteeing Correctness and Availability in P2P Range Indices.
New and emerging P2P applications require sophisticated range query capability and also have strict requirements on query correctness, system availability and item availability. While there has been recent work on developing new P2P range indices, none of these indices guarantee correctness and availability. In this paper, we develop new techniques that can provably guarantee the correctness and availability of P2P range indices. We develop our techniques in the context of a general P2P indexing framework that can be instantiated with most P2P index structures from the literature. As a specific instantiation, we implement P-Ring, an existing P2P range index, and show how it can be extended to guarantee correctness and availability. We quantitatively evaluate our techniques using a real distributed implementation. 1
Automatic Subspace Clustering of High Dimensional Data.
Data mining applications place special requirements on clustering algorithms including: the ability to find clusters embedded in subspaces of high dimensional data, scalability, end-user comprehensibility of the results, non-presumption of any canonical data distribution, and insensitivity to the order of input records. We present CLIQUE, a clustering algorithm that satisfies each of these requirements. CLIQUE identifies dense clusters in subspaces of maximum dimensionality. It generates cluster descriptions in the form of DNF expressions that are minimized for ease of comprehension. It produces identical results irrespective of the order in which input records are presented and does not presume any specific mathematical form for data distribution. Through experiments, we show that CLIQUE efficiently finds accurate clusters in large high dimensional datasets.
Semantic Approximation of Data Stream Joins.
Abstract—We consider the problem of approximating sliding window joins over data streams in a data stream processing system with limited resources. In our model, we deal with resource constraints by shedding load in the form of dropping tuples from the data streams. We make two main contributions. First, we define the problem space by discussing architectural models for data stream join processing and surveying suitable measures for the quality of an approximation of a set-valued query result. Second, we examine in detail a large part of this problem space. More precisely, we consider the number of generated result tuples as the quality measure and we propose optimal offline and fast online algorithms for it. In a thorough experimental study with synthetic and real data, we show the efficacy of our solutions. Index Terms—Data streams, approximation algorithms, semantic load shedding, set approximation error metrics, join processing. 1
MAFIA A Maximal Frequent Itemset Algorithm.
We present a new algorithm for mining maximal frequent itemsets from a transactional database. Our algorithm is especially efficient when the itemsets in the database are very long. The search strategy of our algorithm integrates a depth-first traversal of the itemset lattice with effective pruning mechanisms. Our implementation of the search strategy combines a vertical bitmap representation of the database with an efficient relative bitmap compression schema. In a thorough experimental analysis of our algorithm on real data, we isolate the effect of the individual components of the algorithm. Our performance numbers show that our algorithm outperforms previous work by a factor of three to five. 1
Proceedings of the Tenth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining

How to Quickly Find a Witness.
The subfield of itemset mining is essentially a collection of algorithms. Whenever a new type of constraint is discovered, a specialized algorithm is proposed to handle it. All of these algorithms are highly tuned to take advantage of the unique properties of their associated constraints, and so they are not very compatible with other constraints. In this paper we present a more unified view of mining constrained itemsets such that most existing algorithms can be easily extended to handle constraints for which they were not designed a-priori. We apply this technique to mining itemsets with restrictions on their variance --- a problem that has been open for several years in the data mining community.
WaveScheduling energy%2Defficient data dissemination for sensor networks.
Sensor networks are being increasingly deployed for diverse monitoring applications. Event data are collected at various sensors and sent to selected storage nodes for further in-network processing. Since sensor nodes have strong constraints on their energy usage, this data transfer needs to be energy-efficient to maximize network lifetime. In this paper, we propose a novel methodology for trading energy versus latency in sensor database systems. We propose a new protocol that carefully schedules message transmissions so as to avoid collisions at the MAC layer. Since all nodes adhere to the schedule, their radios can be off most of the time and they only wake up during welldefined time intervals. We show how routing protocols can be optimized to interact symbiotically with the scheduling decisions, resulting in significant energy savings at the cost of higher latency. We demonstrate the effectiveness of our approach by means of a thorough simulation study.
Sketch%2DBased Multi%2Dquery Processing over Data Streams.
Abstract. Recent years have witnessed an increasing interest in designing algorithms for querying and analyzing streaming data (i.e., data that is seen only once in a fixed order) with only limited memory. Providing (perhaps approximate) answers to queries over such continuous data streams is a crucial requirement for many application environments; examples include large telecom and IP network installations where performance data from different parts of the network needs to be continuously collected and analyzed. Randomized techniques, based on computing small “sketch ” synopses for each stream, have recently been shown to be a very effective tool for approximating the result of a single SQL query over streaming data tuples. In this paper, we investigate the problems arising when data-stream sketches are used to process multiple such queries concurrently. We demonstrate that, in the presence of multiple query expressions, intelligently sharing sketches among concurrent query evaluations can result in substantial improvements in the utilization of the available sketching space and the quality of the resulting approximation error guarantees. We provide necessary and sufficient conditions for multi-query sketch sharing that guarantee the correctness of the result-estimation process. We also prove that optimal sketch sharing typically gives rise to N P-hard questions, and we propose novel heuristic algorithms for finding good sketch-sharing configurations in practice. Results from our experimental study with realistic workloads verify the effectiveness of our approach, clearly demonstrating the benefits of our sketch-sharing methodology. 1
Hybrid Push%2DPull Query Processing for Sensor Networks.
Abstract: A powerful database abstraction for sensor networks has recently emerged in which clients program the sensors using a declarative query language. Existing work assumes that data is either pushed from sensor nodes to a gateway, or data is pulled from the gateway through queries. We show that hybrid push-pull data dissemination outperforms the pure approaches and offers significant energy savings. 1
The Architecture of the Cornell Knowledge Broker.

Approximation Techniques for Spatial Data.
Spatial Database Management Systems (SDBMS), e.g., Geographical Information Systems, that manage spatial objects such as points, lines, and hyper-rectangles, often have very high query processing costs. Accurate selectivity estimation during query optimization therefore is crucially important for finding good query plans, especially when spatial joins are involved. Selectivity estimation has been studied for relational database systems, but to date has only received little attention in SDBMS. In this paper, we introduce novel methods that permit high-quality selectivity estimation for spatial joins and range queries. Our techniques can be constructed in a single scan over the input, handle inserts and deletes to the database incrementally, and hence they can also be used for processing of streaming spatial data. In contrast to previous approaches, our techniques return approximate results that come with provable probabilistic quality guarantees. We present a detailed analysis and experimentally demonstrate the efficacy of the proposed techniques. 1.
An Indexing Framework for Peer%2Dto%2DPeer Systems.
Current peer-to-peer (P2P) indices are monolithic pieces of software that address only a subset of the desired functionality for P2P databases. For instance, Chord [6] provides reliability and scalability, but only supports equality queries.
Detecting Change in Data Streams.
Detecting changes in a data stream is an important  area of research with many applications.
A storage and indexing framework for p2p systems.
We present a modularized storage and indexing framework that cleanly separates the functional components of a P2P system, enabling us to tailor the P2P infrastructure to the specific needs of various Internet applications.
P%2Dtree a p2p index for resource discovery applications.
We propose a new distributed, fault-tolerant Peer-to-Peer index structure for resource discovery applications called the P-tree. P-trees can efficiently support range queries in addition to equality queries. 1.
Querying Peer%2Dto%2DPeer Networks Using P%2DTrees.
Peer-to-peer (P2P) systems provide a robust, scalable and decentralized way to share and publish data. However, most existing P2P systems only provide a very rudimentary query facility; they only support equality or keyword search queries over files. We believe that future P2P applications, such as resource discovery on a grid, will require more complex query functionality. As a first step towards this goal, we propose a new distributed, fault-tolerant P2P index structure for resource discovery applications called the P-tree. Ptrees efficiently evaluate range queries in addition to equality queries. We describe algorithms to maintain a P-tree under insertions and deletions of data items/peers, and evaluate its performance using both a simulation and a real distributed implementation. Our results show the efficacy of our approach. 1.
Letter from the Special Issue Editor.
is published quarterly and is distributed to all TC members. Its scope includes the design, implementation, modelling, theory and application of database systems and their technology. Letters, conference information, and news should be
A Vision for PetaByte Data Management and Analyis Services for the Arecibo Telescope.

Privacy preserving mining of association rules.
We present a framework for mining association rules from transactions consisting of categorical items where the data has been randomized to preserve privacy of individual transactions. While it is feasible to recover association rules and preserve privacy using a straightforward &#034;uniform&#034; randomization, the discovered rules can unfortunately be exploited to find privacy breaches. We analyze the nature of privacy breaches and propose a class of randomization operators that are much more effective than uniform randomization in limiting the breaches. We derive formulae for an unbiased support estimator and its variance, which allow us to recover itemset supports from randomized datasets, and show how to incorporate these formulae into mining algorithms. Finally, we present experimental results that validate the algorithm by applying it on real datasets.
Guest Editorial to the special issue on data stream processing.

Leveraging Non%2DUniform Resources for Parallel Query Processing.
Clusters are now composed of non-uniform  nodes with different CPUs, disks or network  cards so that customers can adapt the cluster  configuration to the changing technologies and to  their changing needs. Such modular clusters  challenge parallel databases. The load balancing  techniques used by existing parallel databases  partition data across a set of nodes that all run the  same relational operations. We show in this  paper that this form of load balancing is ill suited  for modular clusters because running the same  operation on different subsets of the data does  not fully utilize non-uniform hardware resources.
Gossip%2DBased Computation of Aggregate Information.
between computers, and a resulting paradigm shift from centralized to highly distributed systems. With massive scale also comes massive instability, as node and link failures become the norm rather than the exception. For such highly volatile systems, decentralized gossip-based protocols are emerging as an approach to maintaining simplicity and scalability while achieving fault-tolerant information dissemination.
Query Processing in Sensor Networks.
Hardware for sensor nodes that combine physical sensors, actuators, embedded processors, and communication components has advanced significantly over the last decade, and made the large-scale deployment of such sensors a reality. Applications range from monitoring applications such as inventory maintenance over health care to military applications.
MAFIA A Performance Study of Mining Maximal Frequent Itemsets.
We present a performance study of the MAFIA algorithm for mining maximal frequent itemsets from a transactional database. In a thorough experimental analysis, we isolate the effects of individual components of MAFIA, including search space pruning techniques and adaptive compression. We also compare our performance with previous work by running tests on very different types of datasets. Our experiments show that MAFIA performs best when mining long itemsets and outperforms other algorithms on dense data by a factor of three to thirty.
Gossip%2DBased Computation of Aggregate Information.
between computers, and a resulting paradigm shift from centralized to highly distributed systems. With massive scale also comes massive instability, as node and link failures become the norm rather than the exception. For such highly volatile systems, decentralized gossip-based protocols are emerging as an approach to maintaining simplicity and scalability while achieving fault-tolerant information dissemination.
Limiting privacy breaches in privacy preserving data mining.
There has been increasing interest in the problem of building accurate data mining models over aggregate data, while protecting privacy at the level of individual records. One approach for this problem is to randomize the values in individual records, and only disclose the randomized values. The model is then built over the randomized data, after first compensating for the randomization (at the aggregate level). This approach is potentially vulnerable to privacy breaches: based on the distribution of the data, one may be able to learn with high confidence that some of the randomized records satisfy a specified property, even though privacy is preserved on average. In this paper, we present a new formulation of privacy breaches, together with a methodology, &#034;amplification&#034;, for limiting them. Unlike earlier approaches, amplification makes it is possible to guarantee limits on privacy breaches without any knowledge of the distribution of the original data. We instantiate this methodology for the problem of mining association rules, and modify the algorithm from [9] to limit privacy breaches without knowledge of the data distribution. Next, we address the problem that the amount of randomization required to avoid privacy breaches (when mining association rules) results in very long transactions. By using pseudorandom generators and carefully choosing seeds such that the desired items from the original transaction are present in the randomized transaction, we can send just the seed instead of the transaction, resulting in a dramatic drop in communication and storage cost. Finally, we define new information measures that take privacy breaches into account when quantifying the amount of privacy preserved by randomization.
How to quickly find a witness.
The subfield of itemset mining is essentially a collection of algorithms. Whenever a new type of constraint is discovered, a specialized algorithm is proposed to handle it. All of these algorithms are highly tuned to take advantage of the unique properties of their associated constraints, and so they are not very compatible with other constraints. In this paper we present a more unified view of mining constrained itemsets such that most existing algorithms can be easily extended to handle constraints for which they were not designed a-priori. We apply this technique to mining itemsets with restrictions on their variance --- a problem that has been open for several years in the data mining community.
Approximate Join Processing Over Data Streams.
We consider the problem of approximating sliding window joins over data streams in a data stream processing system with limited resources. In our model, we deal with resource constraints by shedding load in the form of dropping tuples from the data streams. We first discuss alternate architectural models for data stream join processing, and we survey suitable measures for the quality of an approximation of a set-valued query result. We then consider the number of generated result tuples as the quality measure, and we give optimal offline and fast online algorithms for it. In a thorough experimental study with synthetic and real data we show the efficacy of our solutions. For applications with demand for exact results we introduce a new Archive-metric which captures the amount of work needed to complete the join in case the streams are archived for later processing.
DualMiner A Dual%2DPruning Algorithm for Itemsets with Constraints.
Recently, constraint-based mining of itemsets for questions like &#034;find all frequent itemsets whose total price is at least $50&#034; has attracted much attention. Two classes of constraints, monotone and antimonotone, have been very useful in this area. There exist algorithms that efficiently take advantage of either one of these two classes, but no previous algorithms can efficiently handle both types of constraints simultaneously. In this paper, we present DualMiner, the first algorithm that efficiently prunes its search space using both monotone and antimonotone constraints. We complement a theoretical analysis and proof of correctness of DualMiner with an experimental study that shows the efficacy of DualMiner compared to previous work.
Letter from the Special Issue Editor.
is published quarterly and is distributed to all TC members. Its scope includes the design, implementation, modelling, theory and application of database systems and their technology. Letters, conference information, and news should be
Efficient Approximation of Correlated Sums on Data Streams.
In many applications such as IP network management, data arrives in streams, and queries over those streams need to be processed online using limited storage.
Overview of the 2003 KDD Cup.

Time management for new faculty.

Reminiscences on Influential Papers.

The Cougar Project a work%2Din%2Dprogress report.
Abstract — We present an update on the status of the Cougar Sensor Database Project in which we are investigating a database approach to sensor networks: Clients “program ” the sensors through queries in a high-level declarative language (such as a variant of SQL). In this paper, we give an overview of our activities on energy-efficient data dissemination and query processing. Due to space constraints, we cannot present a full menu of results; instead, we decided to only whet the reader’s appetite with some interesting problems in energy-efficient routing and in-network aggregation and some thoughts on how to approach them. I.
GADT A Probability Space ADT for Representing and Querying the Physical World.
Large sensor networks are being widely deployed for measurement, detection, and monitoring applications. Many of these applications involve database systems to store and process data from the physical world. This data has inherent measurement uncertainties that are properly represented by continuous probability distribution functions (pdf&#039;s). We introduce a new object-relational data type, the Gaussian ADT GADT, that models physical data as gaussian pdf&#039;s, and we show that existing index structures can be used as fast access methods for GADT data. We also present a measure-theoretic model of probabilistic data and evaluate GADT in its light.
Privacy preserving mining of association rules.
We present a framework for mining association rules from transactions consisting of categorical items where the data has been randomized to preserve privacy of individual transactions. While it is feasible to recover association rules and preserve privacy using a straightforward &#034;uniform&#034; randomization, the discovered rules can unfortunately be exploited to find privacy breaches. We analyze the nature of privacy breaches and propose a class of randomization operators that are much more effective than uniform randomization in limiting the breaches. We derive formulae for an unbiased support estimator and its variance, which allow us to recover itemset supports from randomized datasets, and show how to incorporate these formulae into mining algorithms. Finally, we present experimental results that validate the algorithm by applying it on real datasets.
DualMiner a dual%2Dpruning algorithm for itemsets with constraints.
Recently, constraint-based mining of itemsets for questions like &#034;find all frequent itemsets whose total price is at least $50&#034; has attracted much attention. Two classes of constraints, monotone and antimonotone, have been very useful in this area. There exist algorithms that efficiently take advantage of either one of these two classes, but no previous algorithms can efficiently handle both types of constraints simultaneously. In this paper, we present DualMiner, the first algorithm that efficiently prunes its search space using both monotone and antimonotone constraints. We complement a theoretical analysis and proof of correctness of DualMiner with an experimental study that shows the efficacy of DualMiner compared to previous work.
Sequential PAttern mining using a bitmap representation.
We introduce a new algorithm for mining sequential patterns. Our algorithm is especially efficient when the sequential patterns in the database are very long. We introduce a novel depth-first search strategy that integrates a depth-first traversal of the search space with effective pruning mechanisms.
A theoretical framework for learning from a pool of disparate data sources.
Many enterprises incorporate information gathered from a variety of data sources into an integrated input for some learning task. For example, aiming towards the design of an automated diagnostic tool for some disease, one may wish to integrate data gathered in many di#erent hospitals. A major obstacle to such endeavors is that di#erent data sources may vary considerably in the way they choose to represent related data. In practice, the problem is usually solved by a manual construction of semantic mappings and translations between the di#erent sources. Recently there have been attempts to introduce automated algorithms based on machine learning tools for the construction of such translations.
SECRET a scalable linear regression tree algorithm.
Recently there has been an increasing interest in developing regression models for large datasets that are both accurate and easy to interpret. Regressors that have these properties are regression trees with linear models in the leaves, but so far, the algorithms proposed for constructing them are not scalable. In this paper we propose a novel regression tree construction algorithm that is both accurate and can truly scale to very large datasets. The main idea is, for every intermediate node, to use the EM algorithm for Gaussian mixtures to find two clusters in the data and to locally transform the regression problem into a classification problem based on closeness to these clusters. Goodness of split measures, like the gini gain, can then be used to determine the split variable and the split point much like in classification tree construction. Scalability of the algorithm can be enhanced by employing scalable versions of the EM and the classification tree construction algorithms. Tests on real and artificial data show that the proposed algorithm has accuracy comparable to other linear regression tree algorithms but requires orders of magnitude less computation time for large datasets. 1.
Least Expected Cost Query Optimization What Can We Expect%3F

Processing complex aggregate queries over data streams.
Recent years have witnessed an increasing interest in designing algorithms for querying and analyzing streaming data (i.e., data that is seen only once in a fixed order) with only limited memory. Providing (perhaps approximate) answers to queries over such continuous data streams is a crucial requirement for many application environments; examples include large telecom and IP network installations where performance data from different parts of the network needs to be continuously collected and analyzed.
COUGAR the network is the database.
INTRODUCTION  The widespread distribution and availability of small-scale sensors, actuators, and embedded processors is transforming the physical world into a computing platform. One such example is a sensor network consisting of a large number of sensor nodes that combine physical sensing capabilities such as temperature, light, or seismic sensors with networking and computation capabilities [1]. Applications range from environmental control, warehouse inventory, health care to military environments. Existing sensor networks assume that the sensors are preprogrammed and send data to a central frontend where the data is aggregated and stored for o#ine querying and analysis. This approach has two major drawbacks. First, the user cannot change the behavior of the system on the fly. Second, communication in today&#039;s networks is orders of magnitude more expensive than local computation, thus in-network processing can vastly reduce resource usage and thus extend the lifetime of a sensor net
Querying and mining data streams you only get one look a tutorial.

Scaling mining algorithms to large databases.

Querying and Mining Data Streams You Only Get One Look.

Scaling mining algorithms to large databases.

A Framework for Measuring Differences in Data Characteristics.
A data mining algorithm builds a model that captures interesting aspects of the underlying  data. We develop a framework for quantifying the difference, called the deviation, between two  datasets in terms of the models they induce. In addition to being a quantitative, intuitively interpretable  measure of difference, the deviation between two datasets can also be computed very  fast. Our framework covers a wide variety of models including frequent itemsets, decision tree  classifiers, and clusters, and captures standard measures of deviation such as the misclassification  rate and the chi-squared metric as special cases. We also show how statistical techniques  can be applied to the deviation measure to assess whether the difference between two models    Contact author. Supported by a Microsoft Graduate Fellowship.  y  This research was supported by Grant 2053 from the IBM corporation.  z  Supported by Army Research Office grant DAAG55-98-1-0333.  1  is significant (i.e., whether the...
Mining Data Streams under Block Evolution.
Many scientific and commercial applications rely on an immediate processing of transient data streams. In addition to processing queries over streams, their continuative analysis has received more attention recently. Due to specific characteristics of data streams, common analysis techniques known from the area of data mining are not directly applicable to streams. One of the core operations in data analysis is density estimation, which is used for capturing an unknown distribution in various analysis tasks. Modern density estimates base either on kernel functions or wavelets, whereas the wavelet-based ones profit from their ability to identify discontinuities as well as local oscillations. In this paper, we present a new approach to computing wavelet density estimators over data streams. Our estimators allow continuous updates by arrival of new data and provide accurate analytical results, while consuming only a constant amount of memory. Moreover, our estimators are adaptive according to memory as well as CPU usage, i. e., we may change the memory size as well as its computing overhead at runtime. An experimental evaluation proves the feasibility of our approach and shows the superiority of wavelet density estimators compared to their kernel-based counterparts. 1
Report on the SIGKDD 2001 Conference Panel %22New Research Directions in KDD%22.
Two kinds of contemporary developments in cryptography are examined. Widening applications of teleprocessing have given rise to a need for new types of cryptographic systems, which minimize the need for secure key distribution channels and supply the equivalent of a written signature. This paper suggests ways to solve these currently open problems. It also discusses how the theories of communication and computation are beginning to provide the tools to solve cryptographic problems of long standing.
Report on the SIGKDD 2001 Conference Panel %22New Research Directions in KDD%22.
Two kinds of contemporary developments in cryptography are examined. Widening applications of teleprocessing have given rise to a need for new types of cryptographic systems, which minimize the need for secure key distribution channels and supply the equivalent of a written signature. This paper suggests ways to solve these currently open problems. It also discusses how the theories of communication and computation are beginning to provide the tools to solve cryptographic problems of long standing.
The Cougar Approach to In%2DNetwork Query Processing in Sensor Networks.
The widespread distribution and availability of smallscale sensors, actuators, and embedded processors is transforming the physical world into a computing platform. One such example is a sensor network consisting of a large number of sensor nodes that combine physical sensing capabilities such as temperature, light, or seismic sensors with networking and computation capabilities. Applications range from environmental control, warehouse inventory, and health care to military environments. Existing sensor networks assume that the sensors are preprogrammed and send data to a central frontend where the data is aggregated and stored for offline querying and analysis. This approach has two major drawbacks. First, the user cannot change the behavior of the system on the fly. Second, conservation of battery power is a major design factor, but a central system cannot make use of in-network programming, which trades costly communication for cheap local computation.
MAFIA A Maximal Frequent Itemset Algorithm for Transactional Databases.
We present a new algorithm for mining maximal frequent itemsets from a transactional database. Our algorithm is especially efficient when the itemsets in the database are very long. The search strategy of our algorithm integrates a depth-first traversal of the itemset lattice with effective pruning mechanisms. Our implementation of the search strategy combines a vertical bitmap representation of the database with an efficient relative bitmap compression schema. In a thorough experimental analysis of our algorithm on real data, we isolate the effect of the individual components of the algorithm. Our performance numbers show that our algorithm outperforms previous work by a factor of three to five. 1
Bias Correction in Classification Tree Construction.

Advances in decision tree construction.

Towards Sensor Database Systems.
Sensor networks are being widely deployed for measurement,  detection and surveillance applications. In these new applications, users issue  long-running queries over a combination of stored data and sensor data. Most  existing applications rely on a centralized system for collecting sensor data.
On Computing Correlated Aggregates Over Continual Data Streams.
A&amp;$B?6@ 6&amp;(!!&#034;C   198 %D#   F@6)! 280-45380  80  9890-46410  46410  	2= + 28939-4747 /!C&amp;$G# 5!&amp; G# 28779 )IA).J3 &amp;$)JKDL(MN(0OLAPAQ -44320  &#034;/))08!! $&#039;&#039; &#039;  )3 $)0T)!E0&lt;#$)H?6*)7 #$ )&#039;:3&#034;&gt;&#039;  22820-432 ) #U!)&#039;2$)&lt;T!/ # 0  0  ,  &#039; , 	E1V% , 3&#034;0A.    .  240    -4 7-A( , )&#039; 5 S T7  )I*// )/!) $/*&#039;XY6&#034; 0840-40150   10 ))0O!+Z) )&#039;\[&#034;]A^^_)`aAbD_&#034;caddA^_ZdAaAbe_)fE F87g)IA70&lt; $2U/ # 00  / &#034;!!)&#039;JH7  dA &#034;)&#034; ) 710 U h - !( $ O 0   U) 8#(&lt; %(/&#034;T#$  #$U 3&#034;/&#039;A&amp; gS5&#039; 00 )!#$ $)DETiCIA)%7+  )DETiCIA)%7+ 28970 )/!T)W&amp; 530 )TB&amp;  -35950   7(!!)T3&#034;8#$ &#039; #$ 28889  )20 , #!#*   )?E j9B 70-33860 (/&#034;+D(!!)G# !! )TDU  16360-33860   57+  7+ 28969-33860  860  &#034;!)&#039;:// )/!)3&#034;?6#J $&#039;. !-k(&#039; &#039;A$/ ,$&#039;  3 , 2 Ug&#039;   317 l U&amp;    ))0@&amp;$(/: 3&#034;	m7!&#039;k&amp; ! 9360-30720 EJj92)(&#039;  &#034;?6#:#$2)! #$&#034;#((&#039;  &#034;6(&#039;  &#034; 000-296 )/!mKD3&#034;/2&#039;A&amp; H:#$ IA7  2?63R%7g)IA).*3 &amp;...
Query Optimization In Compressed Database Systems.
Over the lastd ecad es, improvements in CPU speed have outpaced improvements in main memory and d isk access rates by ord ers of magnitud , enabling the use ofd ata compression techniques to improve the performance ofd atabase systems. Previous work d scribes the benefits of compression for numerical attributes, whered8 a is stored in compressed  format ond isk. Despite the abund3&amp; e of stringvalued  attributes in relational schemas there is little work on compression for string attributes in ad atabase context. Moreover, none of the previous work suitablyad2 esses the role of the query optimizer: During query execution, dD a is either eagerly d compressed when it is read into main memory, or dD a lazily stays compressed in main memory and is d compressed ond emand only. In this paper, we present an e#ective approach for dD abase compression based on lightweight, attribute-level compression techniques. We propose a Hierarchical ictionary Encod  ing strategy that intelligently selects the most e#ective compression method for string-valued attributes. We show that eager and lazy d compression strategies prod1 e suboptimal plans for queries involving compressed string attributes. We then formalize the problem of compressionaware query optimizationand propose one provably optimal  and two fast heuristic algorithms for selecting a query plan for relational schemas with compressed attributes; our algorithms can easily be integrated into existing cost-based query optimizers. Experiments using TPC-Hd atad emonstrate the impact of our string compression method s and show the importance of compression-aware query optimization. Our approach results in up to an or d r speed up over existing approaches.  1. 
DEMON Mining and Monitoring Evolving Data.
Data mining algorithms have been the focus of much research recently. In practice, the input data to  a data mining process resides in a large data warehouse whose data is kept up-to-date through periodic  or occasional addition and deletion of blocks of data. Most data mining algorithms have either assumed  that the input data is static, or have been designed for arbitrary insertions and deletions of data records.
Report on the Workshop on Research Issues in Data Mining and Knowledge Discovery Workshop %28DMKD 2001%29.

DEMON Mining and Monitoring Evolving Data.
Data mining algorithms have been the focus of much research recently. In practice, the input data to  a data mining process resides in a large data warehouse whose data is kept up-to-date through periodic  or occasional addition and deletion of blocks of data. Most data mining algorithms have either assumed  that the input data is static, or have been designed for arbitrary insertions and deletions of data records.
Data Mining with Decision Trees.
This paper describes the use of decision tree and rule induction in data mining applications. Of methods for classification and regression that have been developed in the fields of pattern recognition, statistics, and machine learning, these areofparticular interest for data mining since they utilize symbolic and interpretable representations. Symbolic solutions can provide a high degree of insight into the decision boundaries that exist in the data, and the logic underlying them. This aspect makes these predictive mining techniques particularly attractive in commercial and industrial data mining applications. We present hereasynopsis  of some major state-of-the-art tree and rule mining methodologies, as well as some recent advances.  Keywords  Decision Tree, Rule Induction, Data Mining  1 Introduction  The use of computer technology in decision support is now widespread and pervasive across a wide range of business and industry. This has resulted in the capture and availability of dat...
RainForest %2D A Framework for Fast Decision Tree Construction of Large Datasets.
Classification of large datasets is an important data mining problem. Many classification algorithms have been proposed in the literature, but studies have shown that so far no algorithm uniformly outperforms all other algorithms in terms of quality. In this paper, we present a unifying framework for decision tree classifiers that separates the scalability aspects of algorithms for constructing a decision tree from the central features that determine the quality of the tree. This generic algorithm is easy to instantiate with specific algorithms from the literature (including C4.5, CART,
Online Scheduling to Minimize Average Stretch.
We consider the classical problem of online job scheduling on uniprocessor and multiprocessor machines. For a given job, we measure the quality of service provided by an algorithm by the stretch of the job, which is defined as the ratio of the amount of time that the job spends in the system to the processing time of the job. For a given sequence of jobs, we measure the performance of an algorithm by the average stretch achieved by the algorithm over all the jobs in the sequence. The average stretch metric has been used to evaluate the performance of scheduling algorithms in many applications arising in databases, networks and systems; however, no formal analysis of scheduling algorithms is known for the average stretch metric.  The main contribution of this paper is to show that the shortest remaining processing time algorithm (SRPT) is O(1)-competitive with respect to average stretch for both uniprocessors as well as multiprocessors. For uniprocessors, we prove that SRPT is 2-competi...
Clustering Large Datasets in Arbitrary Metric Spaces.
Clustering partitions a collection of objects into groups called clusters, such that similar objects fall into the same group. Similarity between objects is defined by a distance function satisfying the triangle inequality; this distance function along with the collection of objects describes a distance space. In a distance space, the only operation possible on data objects is the computation of distance between them. All scalable algorithms in the literature assume a special type of distance space, namely a k-dimensional vector space, which allows vector operations on objects.  We present two scalable algorithms designed for clustering very large datasets in distance spaces. Our first algorithm BUBBLE is, to our knowledge, the first scalable clustering algorithm for data in a distance space. Our second algorithm BUBBLE-FM improves upon BUBBLE by reducing the number of calls to the distance function, which may be computationally very expensive. Both algorithms make only a single scan o...
Classification and Regression Money %2Acan%2A Grow on Trees.

A Framework for Measuring Changes in Data Characteristics.
A data mining algorithm builds a model that captures interesting aspects of the underlying data. We develop a framework for quantifying the difference, called the deviation, between two datasets in terms of the models they induce. Our framework covers a wide variety of models including frequent itemsets, decision tree classifiers, and clusters, and captures standard measures of deviation such as the misclassification rate and the chi-squared metric as special cases. We also show how statistical techniques can be applied to the deviation measure to assess whether the difference between two models is meaningful (i.e., whether the underlying datasets have statistically significant differences in their characteristics), and discuss several practical applications.
BOAT%2DOptimistic Decision Tree Construction.
Classification is an important data mining problem. Given a training database of records, each tagged with a class label, the goal of classification is to build a concise model that can be used to predict the class label of future, unlabeled records. A very popular class of classifiers are decision trees. All current algorithms to construct decision trees, including all main-memory algorithms, make one scan over the training database per level of the tree.  We introduce a new algorithm (BOAT) for decision tree construction that improves upon earlier algorithms in both performance and functionality. BOAT constructs several levels of the tree in only two scans over the training database, resulting in an average performance gain of 300% over previous work. The key to this performance improvement is a novel optimistic approach to tree construction in which we construct an initial tree using a small subset of the data and refine it to arrive at the final tree. We guarantee that any differen...
Mining Very Large Databases.

Rapid Convergence of a Local Load Balancing Algorithm for Asynchronous Rings.
We consider the problem of load balancing in a ring network. We present an  analysis of the following local algorithm. In each step, each node of the ring examines  the number of tokens at its clockwise neighbor and sends a token to the neighbor if the  neighbor has fewer tokens. We show that in a synchronous model, for any initial token  distribution b on an n-node ring, the algorithm converges to a completely balanced  distribution within 4OPT(b)+n steps, where OPT(b) is the time taken by the optimal  centralized algorithm to balance b completely. Our main result is an analysis of the  algorithm in an asynchronous model in which local computations and messages may be  arbitrarily delayed, subject to the constraint that each message is eventually delivered  and each computation is eventually performed. By generalizing our analysis for the  synchronous model, we show that for any initial token distribution b, the algorithm  converges to a completely balanced distribution within 8OPT(b)...
RainForest %2D A Framework for Fast Decision Tree Construction of Large Datasets.
Classification of large datasets is an important data mining problem. Many classification algorithms have been proposed in the literature, but studies have shown that so far no algorithm uniformly outperforms all other algorithms in terms of quality. In this paper, we present a unifying framework for decision tree classifiers that separates the scalability aspects of algorithms for constructing a decision tree from the central features that determine the quality of the tree. This generic algorithm is easy to instantiate with specific algorithms from the literature (including C4.5, CART,
The BUCKY Object%2DRelational Benchmark %28Experience Paper%29.

Rapid Convergence of a Local Load Balancing Algorithm for Asynchronous Rings.
We consider the problem of load balancing in a ring network. We present an  analysis of the following local algorithm. In each step, each node of the ring examines  the number of tokens at its clockwise neighbor and sends a token to the neighbor if the  neighbor has fewer tokens. We show that in a synchronous model, for any initial token  distribution b on an n-node ring, the algorithm converges to a completely balanced  distribution within 4OPT(b)+n steps, where OPT(b) is the time taken by the optimal  centralized algorithm to balance b completely. Our main result is an analysis of the  algorithm in an asynchronous model in which local computations and messages may be  arbitrarily delayed, subject to the constraint that each message is eventually delivered  and each computation is eventually performed. By generalizing our analysis for the  synchronous model, we show that for any initial token distribution b, the algorithm  converges to a completely balanced distribution within 8OPT(b)...
Fair On%2DLine Scheduling of a Dynamic Set of Tasks on a Single Resource.
Consider a set of #tasks&#034; competing for the use of a single #resource&#034;, where: #i# only one task is allowed to use the resource at a time, #ii# the resource is scheduled in unit-time intervals, #iii# each task requires a speci#c fraction of the resource capacityover an extended period, and #iv# tasks arrive and depart at any time. We refer to such a task system as an instance of the single-resource scheduling problem. The problem of designing a #fair&#034; scheduling algorithm for such task systems has recently received a great deal of attention in the literature. This paper makes two main contributions. First, we point out that Tijdeman&#039;s work on the so-called #chairman Preprint submitted to Elsevier Science  assignment problem&#034; provides a simple and e#cient on-line algorithm for the static version of the single-resource scheduling problem #i.e., where the set of tasks competing to use the resource does not change over time#. We then extend Tijdeman&#039;s algorithm to obtain a simple and e#cie...
A proportional share resource allocation algorithm for real%2Dtime
We propose and analyze a proportional share resource allocation algorithm for realizing real-time performance in time-shared operating systems. In a proportional share system, processes are assigned a weight which determines a share (percentage) of the resource they are to receive. The resource is then allocated in discrete-sized time quanta in such a manner that each process makes progress at a precise, uniform rate. Proportional share allocation algorithms are of interest because (1) they provide a natural means of seamlessly integrating real- and non-real-time processing requirements in a general purpose operating system, (2) they are easy to implement (and in particular, easier than more traditional forms of real-time support such as periodic tasks), (3) they provide a simple and effective means of precisely controlling the real-time performance of a process including uniform, predictable degradation in times of system overload, and (4) they provide a natural mean of policing proce...
Fast scheduling of periodic tasks on multiple resources.
Given n periodic tasks, each characterized by an execution requirement and a period, and m identical copies of a resource, the periodic scheduling problem  is concerned with generating a schedule for the n  tasks on the m resources. We present an algorithm that schedules every feasible instance of the periodic scheduling problem, and runs in O(minfm lg n; ng)  time per slot scheduled. 1 Introduction  Given a set \Gamma of n tasks, where each task x is characterized by two integer parameters x:e and x:p, and  m identical copies of a resource, a periodic schedule is one that allocates a resource to each task x in \Gamma for exactly  x:e time units in each interval [k \Delta x:p; (k+1) \Delta x:p)  for all k in N, subject to the following constraints:  Constraint 1: A resource can only be allocated to a task for an entire &#034;slot&#034; of time, where for each  i in N slot i is the unit interval from time i to time i + 1.  Constraint 2: No task may be allocated more than one copy of the resource ...
